#define _CRT_SECURE_NO_WARNINGS

#include "BinaryTree.h"
#include "Queue.h"

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}
int TreeLeafSize(BTNode* root)
{
	if (root == NULL) 
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
int TreeHight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftHight = TreeHight(root->left);
	int rightHight = TreeHight(root->right);

	return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
int TreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* leftroot = TreeFind(root->left, x);
	if (leftroot != NULL)
	{
		return leftroot;
	}
	else 
	{
		return TreeFind(root->right, x);
	}
}
bool isUnivalTree(BTNode* root)
{
	if (root == NULL)
	{
		return true;
	}
	
	if (root->left && root->left->val != root->val)
	{
		return false;
	}
	if (root->right && root->right->val != root->val)
	{
		return false;
	}
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}
bool isSameTree(BTNode* p, BTNode* q) 
{
	if (p == NULL && q == NULL)
	{
		return true;
	}
	if (p || q)
	{
		return false;
	}
	if (p->val != q->val)
	{
		return false;
	}
	else 
	{
		return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	}	
}
bool isSubtree(BTNode* root, BTNode* subRoot) 
{
	if (root == NULL)
	{
		return false;
	}
	if (isSameTree(root, subRoot))
	{
		return true;
	}
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
bool _isSymmetric(BTNode* root1, BTNode* root2)
{
	if (root1 == NULL && root2 == NULL)
	{
		return true;
	}
	if (root1 == NULL || root2 == NULL)
	{
		return false;
	}
	if (root1->val != root2->val)
	{
		return false;
	}

	return _isSymmetric(root1->left, root2->right)
		&& _isSymmetric(root1->right, root2->left);
}
bool isSymmetric(BTNode* root)
{
	if (root == NULL)
	{
		return true;
	}

	return _isSymmetric(root->left, root->right);
}
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->val);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");

	QueueDestroy(&q);
}
bool BinaryTreeComlete(BTNode* root)
{
	assert(root);

	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			break;
		}
	}
	while (!QueueEmpty)
	{
		if (QueueFront(&q) != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}
